package leetcode.dp;

/**
 * @author mazouri
 * @create 2021-09-17 18:42
 * <p>
 * dbbdbc
 * <p>
 * dp[2][4] 代表bdb是否为回文
 */
public class _5_longestPalindrome {
    public String longestPalindrome(String s) {
//        String res = "";
        int start = 0;
        int end = 1;
        boolean[][] dp = new boolean[s.length()][s.length()];

        for (int i = 0; i < dp.length; i++) {
            dp[i][i] = true;
        }

        //字串长度等于2
        for (int i = 0; i < dp.length - 1; i++) {
            if (s.charAt(i) == s.charAt(i + 1)) {
                dp[i][i + 1] = true;
                start = i;
                end = i+2;
               // res = s.substring(i, i + 2);
            } else {
                dp[i][i + 1] = false;
            }
        }

        // 子串长度大于2
        for (int i = 3; i <= dp.length; i++) {
            for (int j = 0; j + i <= dp.length; j++) {
                if (s.charAt(j) == s.charAt(j + i - 1)) dp[j][j + i - 1] = dp[j + 1][j + i - 2];
                else dp[j][j + i - 1] = false;

                if (dp[j][j + i - 1]) {
                   // res = s.substring(j, j + i);
                    start = j;
                    end = j+i;
                }
            }
        }
        return s.substring(start, end);
    }
}
